#define _CRT_SECURE_NO_WARNINGS 1

class RangeFreqQuery {
private:
    int findNum(const vector<int>& arr, int target)
    {
        int left = 0, right = arr.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target)
                right = mid - 1;
            else if (arr[mid] == target)
                return mid + 1;
            else
                left = mid + 1;
        }
        return right + 1;
    }
public:
    RangeFreqQuery(vector<int>& arr) {
        int n = arr.size();
        for (int i = 0; i < n; i++)
        {
            hash[arr[i]].push_back(i);
        }
    }

    int query(int left, int right, int value) {
        const vector<int>& arr = hash[value];
        int l = findNum(arr, left - 1);
        int r = findNum(arr, right);
        return r - l;
    }
    unordered_map<int, vector<int>> hash;
};

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery* obj = new RangeFreqQuery(arr);
 * int param_1 = obj->query(left,right,value);
 */